/*
 * com.future CO.,ltd.
 */
package com.future;

/**
 * Description: 629. K个逆序对数组
 * 给出两个整数 n 和 k，找出所有包含从 1 到 n 的数字，且恰好拥有 k 个逆序对的不同的数组的个数。
 * <p>
 * 逆序对的定义如下：对于数组的第i个和第 j个元素，如果满i < j且 a[i] > a[j]，则其为一个逆序对；否则不是。
 * <p>
 * 由于答案可能很大，只需要返回 答案 mod 109 + 7 的值。
 * <p>
 * 示例 1:
 * <p>
 * 输入: n = 3, k = 0
 * 输出: 1
 * 解释:
 * 只有数组 [1,2,3] 包含了从1到3的整数并且正好拥有 0 个逆序对。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/k-inverse-pairs-array
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @Author: future
 * @Date:2022/3/31:23:35
 */
public class Solution_629 {

    /**
     * 参考图片：img/Solution_629_1.jpg
     * eg:
     * n=3,k=2
     * 组合有：
     * {1,2,3} 0个逆序对
     * {1,3,2} 1个逆序对{3,2}
     * {2,1,3} 1个逆序对{2,1}
     * {2,3,1} 2个逆序对{2,1}{3,1}
     * {3,1,2} 2个逆序对{3,1}{3,2}
     * {3,2,1} 3个逆序对{3,2}{3,1}{2,1}
     * 所以逆序对为2的个数为2
     * <p>
     * 分析：
     * 如 n = 7,k=5，则
     * 求 dp[5][3] ，表示长度为1...5,逆序对的个数为3的个数
     * 情况1：dp[4][3],4123，把 5直接拼到后面为41235,此时增加逆序对个数为0，因为原本4123逆序对个数为3,所以为dp[4][3]
     * 情况2：dp[4][2],1423，把 5直接拼到位置为14253,此时增加逆序对个数为+1，因为原本1423逆序对个数为2，所以为dp[4][2]
     * 情况3：dp[4][1],1243，把 5直接拼到位置为12543,此时增加逆序对个数为+2，因为原本1243逆序对个数为1，所以为dp[4][1]
     * 情况4：dp[4][0],1234，把 5直接拼到位置为15234,此时增加逆序对个数为+3，因为原本1234逆序对个数为0，所以为dp[4][0]
     * 情况1~4加起来就是dp[5][3]的答案
     * <p>
     * 计算dp[i][j]
     * j<i时，dp[i][j]=dp[i-1][j]+dp[i][j-1]
     * 推导如下
     * eg:
     * dp[5][3]=dp[4][3]+dp[4][2]+dp[4][1]+dp[4][0]
     * dp[5][4]
     * = dp[4][4]+dp[4][3]+dp[4][2]+dp[4][1]+dp[4][0]
     * = dp[4][4]+dp[5][3]
     * 推导出==>dp[i][j]=dp[i-1][j]+dp[i][j-1]
     * j>=i时，dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-i]
     * 推导如下
     * eg:
     * dp[5][7] = dp[4][7]+dp[4][6]+dp[4][5]+dp[4][4]+dp[4][3]
     * (注意：这里为什么不继续dp[4][2]...dp[4][0],因为总共才4个数，加一个最多也就+4，那么逆序对基数至少7-4=3，所以加到dp[4][3]为止)
     * dp[5][8]
     * = dp[4][8]+( dp[4][7]+dp[4][6]+dp[4][5]+dp[4][4] )
     * = dp[4][8] + dp[5][7]-dp[4][3]
     *
     * @param n
     * @param k
     * @return
     */
    public static int kInversePairs(int n, int k) {
        if (n < 1 || k < 0) {
            return 0;
        }
        int[][] dp = new int[n + 1][k + 1];
        dp[0][0] = 1;
        int mod = 1000000007;// 题目要求
        for (int i = 1; i <= n; i++) {
            dp[i][0] = 1;
            for (int j = 1; j <= k; j++) {
                dp[i][j] = (dp[i][j - 1] + dp[i - 1][j]) % mod;
                if (j >= i) {
                    /**
                     * 防止前面mod之后，结果为3，如果后面dp[i-1][j-i]=7，则出现3-7<0的情况，所以做了如下改进
                     */
                    dp[i][j] = (dp[i][j] - dp[i - 1][j - i] + mod) % mod;
                }
                // 考虑到溢出问题，一下不行
               /* if (j < i) {
                    dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
                } else {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - i];
                }*/
            }
        }
        return dp[n][k];
    }

    public static int kInversePairs2(int n, int k) {
        if (n < 1 || k < 0) {
            return 0;
        }
        int[][] dp = new int[n + 1][k + 1];
        dp[0][0] = 1;
        int mod = 1000000007;// 题目要求
        for (int i = 1; i <= n; i++) {
            dp[i][0] = 1;
            for (int j = 1; j <= k; j++) {
                dp[i][j] = (dp[i][j - 1] + dp[i - 1][j]) % mod;
                if (j >= i) {
                    /**
                     * 防止前面mod之后，结果为3，如果后面dp[i-1][j-i]=7，则出现3-7<0的情况，所以做了如下改进
                     */
                    dp[i][j] = (dp[i][j] - dp[i - 1][j - i] + mod) % mod;
                }
            }
        }
        return dp[n][k];
    }


    public static void main(String[] args) {
        int n = 5, k = 4;
        System.out.println(kInversePairs(n, k));
    }

}
